package com.berchen.数据结构.单链表;

import java.util.Stack;

/**
 * 单链表
 */
public class SingleLinketList {

    private Node head;  // 头节点

    public SingleLinketList() {
    }

    /**
     * 判断该链表是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return head == null;
    }

    /**
     * 往单链表中添加数据
     *
     * @param node
     * @return
     */
    public void add(Node node) {
        if (isEmpty()) {
            head = node;
        } else {
            Node temp = head;
            // 循环找到链表的最后节点
            while (temp.next != null) {
                // 一个节点一个节点往后移动
                temp = temp.next;
            }
            temp.next = node;
        }
    }

    /**
     * 删除元素
     *
     * @param no
     * @return
     */
    public Node delete(int no) {

        if (isEmpty()) return null;
        Node temp = head;
        if (temp.getNo() == no) {
            head = head.next;
            return temp;
        }
        while (temp.next != null) {
            if (temp.next.getNo() == no) {
                Node delNode = temp.next;
                temp.next = temp.next.next;
                return delNode;
            }
            temp = temp.next;
        }
        return null;
    }

    /**
     * 获取倒数第k个元素
     *
     * @param k
     * @return
     */
    public Node getNode(int k) {

        if (k > getCount() || k <= 0) throw new RuntimeException("超出链表长度");
        if (k == getCount()) return head;
        int length = 1;
        Node temp = head;
        while (temp != null) {
            if (getCount() - k + 1 == length) {
                return temp;
            }
            temp = temp.next;
            length++;
        }
        return null;
    }

    /**
     * 将链表反转
     * 读取旧链表的节点 读取后放入一个新链表中，并且放入的元素都是插入到第一个位置
     */
    public void reverse() {
        if (isEmpty()) throw new RuntimeException("链表为空");
        if (head.next == null) return;  // 一个节点不需要反转
        Node temporary = new Node(0, ",", "");// 新链表的头节点 该头节点无实际意义
        Node temp = head;             // 当前节点
        Node tempNext = head.next;    // 指向当前节点的下一个节点
        while (temp != null) {

            temp.next = temporary.next;
            temporary.next = temp;

            temp = tempNext;
            if (tempNext != null) {
                tempNext = tempNext.next;
            }
        }
        head = temporary.next;
    }

    public Node getHead() {
        return head;
    }

    /**
     * 从尾到头打印链表  利用递归
     * @param node
     */
    public void listEndToStart(Node node){

        if(node==null){
            return;
        }
        if(node.next==null){
            System.out.println(node);
            return; // 先打印后结束
        }else {
            listEndToStart(node.next);  // 递归后面打印
            System.out.println(node);
        }
    }

    /**
     * 从尾到头打印链表 利用栈
     */
    public void listStack(){

        if(isEmpty()) return;
        Node temp=head;
        Stack<Node> stack=new Stack<>();
        while (temp!=null) {
            stack.push(temp);
            temp=temp.next;
        }
        // 打印
        while (!stack.empty()) {
            System.out.println(stack.pop());
        }
    }

    /**
     * 获取单链表中节点的个数
     *
     * @return
     */
    public int getCount() {
        if (isEmpty()) return 0;
        Node temp = head;
        int count = 0;
        while (temp != null) {
            count++;
            temp = temp.next;
        }
        return count;
    }


    /**
     * 根据node的no作为条件进行修改
     *
     * @param node
     * @return
     */
    public boolean update(Node node) {
        if (isEmpty()) return false;
        Node temp = head;
        while (temp != null) {
            if (temp.getNo() == node.getNo()) {
                temp.setName(node.getName());
                temp.setNickName(node.getNickName());
                return true;
            }
            temp = temp.next;
        }
        return false;

    }

    /**
     * 显示单链表
     */
    public void list() {
        if (isEmpty()) throw new RuntimeException("链表为空");
        Node temp = head;
        while (temp != null) {
            System.out.println(temp.toString());
            temp = temp.next;
        }
    }
}
